class Solution {
public:
    pair<bool, bool> dp[35][35][35][35];
    bool isScramble(string s1, string s2) {
        return dfs(0, s1.size() - 1, 0, s2.size() - 1, s1, s2);
    }
    bool dfs(int l1, int r1, int l2, int r2, string& s1, string& s2)
    {
        if (l1 == r1) return s1[l1] == s2[l2];
        if (dp[l1][r1][l2][r2].second) return dp[l1][r1][l2][r2].first;
        for (int i = l1; i < r1; i++)
        {
            int temp1 = i - l1 + 1, temp2 = r1 - i;
            if (dfs(l1, i, l2, l2 + temp1 - 1, s1, s2) && dfs(i + 1, r1, r2 - temp2 + 1, r2, s1, s2))
            {
                dp[l1][r1][l2][r2].second = 1;
                return dp[l1][r1][l2][r2].first = 1;
            }
            if (dfs(l1, i, r2 - temp1 + 1, r2, s1, s2) && dfs(i + 1, r1, l2, l2 + temp2 - 1, s1, s2))
            {
                dp[l1][r1][l2][r2].second = 1;
                return dp[l1][r1][l2][r2].first = 1;
            }
        }
        dp[l1][r1][l2][r2].second = 1;
        return dp[l1][r1][l2][r2].first = 0;
    }
};